package chapter3_array;

/**
 * 无序数组中寻找第几个大的元素
 */
public class KthLargestElement {

    public static int findKthLargest(int[] nums, int k) {
        return search(nums, 0, nums.length - 1, k);
    }

    static int search(int[] nums, int l, int r, int k) {
        int partition = partition(nums, l, r);
        if (nums.length - partition < k) {
            return search(nums, l, partition - 1, k);
        } else if (nums.length - partition > k) {
            return search(nums, partition + 1, r, k);
        } else {
            return nums[partition];
        }
    }

    static int partition(int[] nums, int l, int r) {
        int e = nums[l];
        int i = l + 1, j = r;
        while (true) {
            while (i <= r && nums[i] < e) {
                i++;
            }
            while (j >= l && nums[j] > e) {
                j--;
            }
            if (i > j) {
                break;
            }
            swap(nums, i++, j--);
        }
        swap(nums, j, l);
        return j;
    }

    static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {-100,100, 1, 2, 3, 4, 2, 3, 4, 5, 6, 7};
        System.out.println(findKthLargest(arr, 1));
    }
}
